This invention relates to pattern matching and, more particularly, to a network for matching an input vector signal to a set of vector signals stored within the network.
A wide variety of applications exist in which it is desirable for a machine to automatically recognize, analyze and classify signal patterns. One such application, for example, is found in the field of imaged character recognition. That is, printed fonts, or hand written characters are presented to the character recognition system, and the task is to identify the characters. Often, such identification can be made through pattern matching of the signals representing the characters with some preset templates. One such system is disclosed in a copending application, filed on Dec. 20, 1988, entitled "Imaged Symbol Classification". Another such system is described in U.S. Pat. No. 4,259,661 issued Mar. 31, 1981.
Another area where template matching is very useful is in connection with associative memory. When using an associative memory, the user generally knows only a portion of the desired output signal, or knows the desired signal imperfectly. Template matching permits the system to identify the closest match to a set of stored signals.
Digital computers are ubiquitous and quite powerful, but they do exhibit certain limitations in problem solving. Many classes of problems take such an enormous amount of computation that a solution in real time is not practically possible. Pattern recognition, generally, and template matching, in particular, are examples of such problems.
Until recently, most artisans either suffered the limitations of general purpose digital computers or developed special purpose digital computers to solve their particular problems more efficiently.
On Apr. 21, 1987, U.S. Pat. No. 4,660,166 titled "Electronic Network for Collective Decision Based on Large Number of Connections Between Signals" was issued to J. J. Hopfield, and it renewed efforts to find a compact solution to pattern matching, among others. Hopfield disclosed a generalized circuit having N amplifiers of high gain and an N.times.N interconnection matrix having N input conductors and N output conductors. The amplifiers exhibit a sigmoid input-output relation, with a minimum and maximum possible output which can be thought of as a "0" and a "1". Each input conductor of the interconnection matrix is connected to the input of a separate one of the amplifiers, and each amplifier has its output terminals (positive and negative) connected to a separate one of the matrix output conductors. Each amplifier has in addition an input capacitance and resistance. Within the interconnection matrix, each input conductor is connected to an output conductor through a resistor.
When used as an associative memory circuit, the input signals that represent the known portion of the information desired are applied to the amplifiers. This alters the state of the circuit. Once the circuit's state is altered, the amplifiers in combination with the feedback interconnection network drive the circuit to a new stable state. The new state produces a unique output that corresponds to the sought information.
Since the amplifiers have a high gain, the alteration in the circuit's state drives the circuit to one of a set of predetermined stable states which presents an output pattern of binary 1's and 0's at the amplifiers' outputs. The state to which the circuit is driven is dictated by the collection of the resistor values in the feedback interconnection network. The values are analog quantities.
The circuit has the potential for being very compact because the only active elements are the amplifiers, and the structure is very regular. On the other hand, creating resistors in semiconductor technology with accurate values is not easy. Furthermore, wide dynamic range for such resistors is difficult to achieve. That is, it is difficult to create both resistors of very low values and resistors of very high values.
Another difficulty relates to the fact that in a semiconductor IC realization of this circuit, it is difficult to alter the values of the resistors. Furthermore, a modification to even one of the templates that are stored in the interconnection network results in required changes to all of the resistors. The reason for this is that the information about the stored templates is distributed throughout the interconnection network.
These problems were solved with a circuit disclosed in a copending application by H. P. Graf titled "A Computation Network," which was filed in the U.S. Patent Office on Jan. 20, 1987, and bears the Ser. No. 005,248, now U.S. Pat. No. 4,901,271. It contains two networks that store the templates, and an n-tuple network. The three networks are circularly connected. In the Graf network, the stored templates are not comingled and, therefore, the storage of the template information can take on the binary values of the templates. The storage is realized with flip-flops, dedicated to each bit. Means are also disclosed for implementing the process of storing the information in those bits, and for thereby altering the stored information. Each of the template-storing networks merely contains a set of input busses and a set of output busses. Each of the input busses contributed to the output of each of the output busses under control of the flip-flops that store the templates. In one of the template-storing networks, a template is stored in the flip-flops that control a particular output bus. In the other template-storing network, a template is stored in the flip-flops that control a particular input bus.
Pattern matching received a boost from another direction with recent advances in the field of connectionism. Specifically, highly parallel computation networks ("neural networks") have come to the fore with learning algorithms for multi-layered networks in which "hidden" layers of neural elements permit separation of arbitrary regions of the feature space. Use of such a network has indeed been applied to the character classification process, as described, for example, by Gullichsen et al. in "Pattern Classification by Neural Networks: An Experimental System for Icon Recognition", Proceedings of the IEEE First International Conference on Neural Networks, pp IV--725-732, Cardill et al., Editors.
Like the aforementioned Hopfield circuit, these circuits require the ability to multiply input signals by an analog value, and the ability to add the resultant products.
In the charge coupled device (CCD) art, storage of information has been accomplished by recognizing that electric charge can be stored not only in discrete capacitors but also in spatially defined areas of electric potential minima within a semiconductor material. The storage site can be accessed, and location of the site can be changed within the semiconductor in, at least, two dimensions. Thus, electric charge can be stored and moved. One example of such storage devices is found in U.S. Pat. No. 3,858,232, issued to Boyle et al. on Dec.31, 1974.